package 题目集.倍增算法.lca;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

/**
 * https://www.luogu.com.cn/problem/P3379
 * 这题的附加数据有点毒，java递归会爆栈，需要手动模拟递归。
 */
public class ch02_倍增跳法 {
    static int[][] parent;//保存每个节点的父节点，parent[i][j]表示i的2^j的父节点
    static int[] depth;//保存每个节点的深度
    static int n, m, s;
    static int power;
    static int MAXN = 500010;
    // 定义图的邻接表表示
    static List<Integer>[] graph = new ArrayList[MAXN];

    public static void main(String[] args) {
        Reader sc = new Reader(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        s = sc.nextInt();
        power = (int) Math.ceil(Math.log(n) / Math.log(2));  //倍增的最大次数
        parent = new int[n + 1][power];
        depth = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        dfs(s, s);  //根节点的父节点是自己
        build();

        for (int i = 1; i <= m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            System.out.println(lca(u, v));
        }
    }

    public static void dfs(int u, int fa) {
        depth[u] = depth[fa] + 1;
        parent[u][0] = fa;
        for (Integer v : graph[u]) {
            if (fa == v) continue;
            dfs(v, u);
        }
    }

    public static void build() {
        for (int j = 1; j < power; j++) {
            for (int i = 1; i <= n; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }

    public static int lca(int u, int v) {
        if (depth[u] < depth[v]) { //保证u在v下面
            int temp = u;
            u = v;
            v = temp;
        }
        //u先上升到和v一样的高度
        if (depth[u] != depth[v]) u = up(u, depth[v]);
        //如果u=v，说明v是u的祖先
        if (u == v) return u;
        //st表逼近公共祖先
        for (int i = power - 1; i >= 0; i--) {
            if (parent[u][i] != parent[v][i]) {
                u = parent[u][i];
                v = parent[v][i];
            }
        }
        return parent[u][0];
    }

    /**
     * 求高度为h的，节点u的祖先
     */
    public static int up(int u, int h) {
        //st表逼近dept[v]
        for (int i = power - 1; i >= 0; i--) {
            if (depth[parent[u][i]] > h) {  //是逼近h，所以不能等于
                u = parent[u][i];
            }
        }
        return parent[u][0];    //上面是逼近h的高度，这里是抵达h的高度，
    }

    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public static int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
